W3. Finite State Automata, Formal Definitions, Language Recognition

1. Summary

1.1 Historical Background

The theory of finite state automata emerged in the 1940s–1960s through the contributions of several researchers:

• Warren McCulloch and Walter Pitts (1943): Published the first mathematical model of a neural network using finite automata-like structures, demonstrating that neurons performing logical operations could be modeled as finite state machines.
• Stephen Kleene (1951): Formalized regular events and proved the equivalence between finite automata and regular expressions, establishing the algebraic foundation of the theory.
• Edward F. Moore (1956): Introduced the Moore machine, a transducer whose output depends only on the current state.
• George H. Mealy (1955): Introduced the Mealy machine, a transducer whose output depends on both the current state and the current input symbol.
• Michael O. Rabin and Dana Scott (1959): Published the landmark paper “Finite Automata and Their Decision Problems,” introducing non-deterministic finite automata (NFAs) and proving their equivalence with deterministic ones. This work earned them the Turing Award in 1976.

These foundational results established FSAs as a central model in theoretical computer science, compiler design, and formal language theory.

1.2 FSA vs. Turing Machine

A Turing machine is a much more powerful computational model: it has an infinite tape that serves as unbounded memory, allowing it to solve problems that FSAs cannot. However, this generality comes at a practical cost:

• FSAs have only finite memory (the current state encodes all available information). They are simple, fast, and suitable for pattern recognition in streams of data.
• Turing machines require potentially infinite memory, which is unrealizable in physical hardware.

For many real-world engineering tasks — lexical analysis, protocol validation, hardware controllers, network packet filtering — the patterns to be recognized are regular: they do not require counting to arbitrary depths or remembering unbounded history. An FSA is sufficient and far more efficient. The Turing machine’s unlimited power is unnecessary for such tasks and introduces unneeded complexity.

Key principle: Use the simplest computational model that is sufficient for the task. For regular patterns, FSAs are the appropriate tool.

1.3 What is a Finite State Automaton?

A Finite State Automaton (FSA), also called a finite state machine, is a mathematical model of computation used to recognize patterns and process sequences of symbols. It is one of the simplest yet most powerful computational models. An FSA is an abstract machine that operates by:

1. Starting in a designated initial state
2. Reading input symbols one at a time from an alphabet (a set of allowed symbols)
3. Transitioning between states based on the input symbol and current state
4. Either accepting or rejecting the input depending on whether we end in an accepting (final) state

Think of an FSA as a very simple computer that has only a fixed amount of memory—just enough to remember which of its finite states it is currently in. It cannot store arbitrary information, but it can recognize patterns that follow regular rules.

1.4 Real-World Examples

FSAs are everywhere in computer science:

• Vending machines: Different states represent different amounts of money inserted. Each coin transitions you to a new state.
• Traffic lights: States are Red, Yellow, Green. Time-based inputs trigger transitions.
• Lexical analyzers (lexers): In compilers, FSAs identify tokens like identifiers, keywords, and numbers in source code.
• Video game characters: AI behavior like “Wander,” “Chase,” “Flee” are states with transitions triggered by events.
• Text parsing: Recognizing patterns in text documents.
• Protocol analysis: Validating sequences of network messages.

1.5 Informal Introduction with Examples

Example: A Turnstile (subway gate)

Imagine a turnstile that controls access to a subway:

• States: Locked (can’t pass) and Unlocked (can pass)
• Initial state: Locked
• Accepting state: Locked (the system is in the correct state)
• Alphabet: {Push, Coin}
• Transitions:
  • From Locked: If you insert a Coin → go to Unlocked. If you Push → stay Locked.
  • From Unlocked: If you Push → go to Locked (you pass through). If you insert a Coin → stay Unlocked.

This simple FSA models the turnstile’s behavior completely.

1.6 Formal Definition of a Finite State Automaton

A deterministic finite automaton (DFA) is formally defined as a 5-tuple:

\[M = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q\): A finite set of states. Example: \(Q = \{\text{Locked}, \text{Unlocked}\}\) or \(Q = \{q_0, q_1, q_2, q_3, q_4\}\)
• \(\Sigma\): A finite set of input symbols called the alphabet. Example: \(\Sigma = \{0, 1\}\) (binary) or \(\Sigma = \{a, b, c\}\)
• \(\delta\): The transition function that defines how the machine moves between states. It is a function \(\delta: Q \times \Sigma \rightarrow Q\), meaning: given a state \(q\) and an input symbol \(\sigma\), it tells us which state to move to next. If the transition function is defined for all pairs \((q, \sigma)\), the FSA is called complete. Otherwise, it is incomplete.
• \(q_0\): The initial (starting) state, where \(q_0 \in Q\). This is where the machine begins.
• \(F\): A set of accepting (final) states, where \(F \subseteq Q\). A string is accepted if the machine ends in one of these states.

Deterministic means that for each state and input symbol, there is exactly one next state. This is in contrast to non-deterministic FSAs (NFAs), where there can be multiple possible next states, but we focus on deterministic FSAs here.

1.7 Reading a String with an FSA

Given a string (sequence of symbols) \(s = c_1c_2...c_n\), the FSA processes it as follows:

1. Start at the initial state \(q_0\)
2. Read the first symbol \(c_1\) and transition to state \(\delta(q_0, c_1)\)
3. Read the second symbol \(c_2\) and transition to state \(\delta(\delta(q_0, c_1), c_2)\)
4. Continue until all symbols are read
5. If the final state is in \(F\) (an accepting state), the string is accepted. Otherwise, it is rejected.

1.8 Extended Transition Function

To formalize the idea of processing an entire string, we define the extended transition function \(\delta^*\):

\[\delta^*: Q \times \Sigma^* \rightarrow Q\]

This function processes an entire string (not just a single symbol). It is defined recursively:

1. Base case: \(\delta^*(q, \epsilon) = q\) (processing the empty string keeps you in the same state)
2. Recursive case: For any string \(y\) and symbol \(\sigma\), \(\delta^*(q, y\sigma) = \delta(\delta^*(q, y), \sigma)\) (process \(y\), then process \(\sigma\))

This definition formalizes the step-by-step process described above.

1.9 Accepting Strings and Languages

• A string \(x\) is accepted by FSA \(M\) if \(\delta^*(q_0, x) \in F\) (the final state is an accepting state)
• A string is rejected by FSA \(M\) if the final state is not in \(F\) (or if the transition is undefined in an incomplete FSA)
• The language accepted by \(M\), denoted \(L(M)\), is the set of all strings that \(M\) accepts: \(L(M) = \{x \in \Sigma^* \mid \delta^*(q_0, x) \in F\}\)
• A language \(L\) is called regular if there exists some FSA \(M\) such that \(L = L(M)\)

1.10 Complete vs. Incomplete FSAs

• Complete FSA: The transition function \(\delta\) is total, meaning \(\delta(q, \sigma)\) is defined for every state \(q \in Q\) and every symbol \(\sigma \in \Sigma\). Every string can be processed without getting “stuck.”
• Incomplete FSA: The transition function is partial, meaning some transitions are not defined. If a string tries to follow an undefined transition, the FSA rejects that string (because we cannot reach a final state).

To convert an incomplete FSA to a complete one, we typically add a trap state (or error state) that all undefined transitions lead to. This trap state is non-accepting, and once entered, the machine stays there (usually with a self-loop).

1.11 Graphical Representation

FSAs are commonly shown as state diagrams:

• States are represented as circles (or rounded rectangles)
• An incoming arrow from nowhere points to the initial state \(q_0\)
• Accepting states are shown as double circles
• Transitions are shown as arrows labeled with the input symbol(s)
• A self-loop is an arrow from a state back to itself

Standard FSA state-diagram notation

1.12 Deterministic vs. Non-Deterministic FSAs

• Deterministic FSA (DFA): For each state and input symbol, there is exactly one next state. This is what we formally defined above.
• Non-deterministic FSA (NFA): For a given state and input symbol, there may be zero, one, or multiple possible next states. Or there may be transitions on the empty string (epsilon transitions).

While NFAs are more expressive in notation, any NFA can be converted to an equivalent DFA. In this course, we focus on deterministic FSAs.

1.13 Finite Languages vs. Infinite Languages

Finite languages are sets containing only finitely many strings. For example, \(L = \{1, 00, 0101\}\) has exactly three strings. Any finite language is regular and can always be accepted by some FSA. The construction is straightforward: represent the language as a binary tree of states, one branch per string, where each edge corresponds to the next symbol and each leaf (terminal node) that corresponds to a word in \(L\) is made an accepting state. Because the language is finite, the tree has a finite number of nodes, and the resulting FSA is well-defined.

Infinite languages are sets with infinitely many strings. Not all infinite languages are regular, but many are. Two canonical examples of infinite languages that can be recognized by an FSA are:

• Strings starting with “0”: \(L = \{0w \mid w \in \{0,1\}^*\}\). An FSA needs only two states: a non-accepting start state \(q_0\) that transitions to an accepting state \(q_1\) on input \(0\), where \(q_1\) loops on both \(0\) and \(1\). This language is infinite (there are infinitely many strings starting with \(0\)) yet perfectly regular.
• The language \((ab)^k\): \(L = \{(ab)^k \mid k \geq 0\} = \{\epsilon, ab, abab, ababab, \ldots\}\). An FSA with three states can recognize it: start and accept at \(q_0\), transition \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0\), with all other transitions going to a non-accepting trap state.

By contrast, the language \(L = \{a^k b^k \mid k \in \mathbb{N}\}\) (equal numbers of \(a\)’s followed by equal numbers of \(b\)’s) is infinite and not regular. To accept it, a machine would need to remember the exact value of \(k\), which requires unbounded memory. Since an FSA has only a finite number of states, it cannot count to an arbitrary \(k\) and will fail for sufficiently large inputs. This is formalized by the Pumping Lemma for regular languages.

1.14 Applications in Compilers

FSAs are crucial in lexical analysis, the first phase of compilation:

1. A lexer (or scanner) reads source code character by character
2. It uses FSAs to identify tokens: identifiers, keywords, numbers, operators, punctuation
3. For example, an identifier in most programming languages starts with a letter, followed by any number of letters or digits
4. An FSA can recognize this pattern: start state → (letter) → accepting state → (letter/digit)* loop → accepting state

A lexer generator tool like lex takes regular expressions (which describe regular languages) and automatically generates an FSA (and lexer code) that recognizes those patterns.

1.15 Finite State Transducers

A Finite State Transducer (FST) is an extension of FSAs that produces output in addition to accepting/rejecting input. Instead of just a tape of input, an FST has:

• An input tape with symbols from an input alphabet
• An output tape where it writes symbols from an output alphabet
• Transitions labeled with \(i/o\) (read \(i\), write \(o\))

FSTs are useful for:

• Compiling source code to target code
• Translating between languages
• Compression and decompression
• Pattern replacement in text

An FST is formally defined as the 7-tuple:

\[T = \langle Q, I, O, \delta, q_0, F, \eta \rangle\]

where:

• \(Q\) is a finite set of states
• \(I\) is the finite input alphabet
• \(O\) is the finite output alphabet
• \(\delta: Q \times I \rightarrow Q\) is the state transition function
• \(q_0 \in Q\) is the initial state
• \(F \subseteq Q\) is the set of accepting (final) states
• \(\eta: Q \times I \rightarrow O^*\) is the output function — for each state and input symbol it specifies the string of output symbols produced during that transition

The transduction relation computed by \(T\) is denoted \(\tau\). Given an input string \(x \in I^*\), if \(T\) accepts \(x\) and produces output string \(y \in O^*\) during processing, we write:

\[y = \tau(x)\]

In general, \(\tau \subseteq I^* \times O^*\) is a relation (not necessarily a function, since an FST may be non-deterministic and produce different outputs for the same input). When \(T\) is deterministic, \(\tau\) is a partial function from \(I^*\) to \(O^*\).

1.16 Abstraction and Communication

A critical skill for a computer scientist — and more broadly for any engineer — is the ability to move fluidly between two levels of description:

• Informal (intuitive) description: A narrative or diagram that conveys the intent of a system to a human reader without requiring mathematical precision. Example: “the turnstile unlocks when you insert a coin.”
• Formal (mathematical) description: A rigorous specification using agreed-upon notation that is unambiguous and can be reasoned about mechanically. Example: the 5-tuple \(M = (Q, \Sigma, \delta, q_0, F)\) with an explicit transition table.

The ability to translate between these two levels — abstraction — is what allows a programmer to understand a client’s informal requirements and implement them as correct, verifiable code. Without abstraction, informal ideas remain vague; without grounding in formalism, mathematical objects remain disconnected from reality.

Connection to Aristotle’s Rhetorical Triangle. Effective communication of technical ideas requires balancing three elements, described by Aristotle:

Element	Meaning	In a technical context
Logos (logic)	The argument’s logical content and structure	The formal definition, proof, or algorithm
Ethos (credibility)	The speaker’s authority and trustworthiness	Citation of established results, rigorous notation
Pathos (emotion/audience)	Connection with the audience’s perspective	Intuitive examples, analogies, motivation

A good technical explanation combines all three: a solid formal argument (Logos), grounded in established theory (Ethos), presented with examples and motivation that resonate with the audience (Pathos). Understanding this balance helps programmers communicate specifications, designs, and proofs to colleagues, clients, and formal verification tools alike.

---

2. Definitions

• Alphabet (\(\Sigma\)): A finite set of symbols from which strings are formed.
• String: A sequence of zero or more symbols from an alphabet. The empty string is denoted \(\epsilon\).
• State: A configuration or condition of the FSA. The machine is always in exactly one state at any moment.
• Initial State (\(q_0\)): The state where the FSA begins processing any input string.
• Accepting State (Final State): A state that, if the FSA is in this state after reading the entire input, causes the string to be accepted. The set of all accepting states is denoted \(F\).
• Transition Function (\(\delta\)): A function \(\delta: Q \times \Sigma \rightarrow Q\) that specifies, for each state and input symbol, which state to move to next. If partial, some transitions may be undefined.
• Complete FSA: An FSA where the transition function \(\delta\) is defined for all pairs \((q, \sigma) \in Q \times \Sigma\).
• Incomplete FSA: An FSA where the transition function \(\delta\) is not defined for all pairs; some transitions are missing.
• Extended Transition Function (\(\delta^*\)): A generalization of \(\delta\) that processes entire strings instead of single symbols, defined recursively: \(\delta^*(q, \epsilon) = q\) and \(\delta^*(q, y\sigma) = \delta(\delta^*(q, y), \sigma)\).
• Language: A set of strings over an alphabet. Languages can be finite or infinite.
• Regular Language: A language that is accepted by some finite state automaton.
• Deterministic Finite Automaton (DFA): An FSA where each state has at most one outgoing transition for each symbol (no non-determinism).
• Non-Deterministic Finite Automaton (NFA): An FSA where a state can have multiple outgoing transitions for the same symbol, or transitions on the empty string.
• Trap State (Error State): A non-accepting state added to make an FSA complete. All undefined transitions lead to the trap state. Once entered, the machine typically loops in the trap state.
• Finite State Transducer (FST): An FSA extended with an output tape and output function, used to translate between input and output languages.
• Lexer (Scanner): A program that reads text character by character and uses FSAs to identify tokens (identifiers, keywords, numbers, etc.) in the text.

---

3. Formulas

• Transition Function: \(\delta: Q \times \Sigma \rightarrow Q\) where \(\delta(q, \sigma)\) gives the next state from state \(q\) upon reading symbol \(\sigma\)
• Extended Transition Function (Base): \(\delta^*(q, \epsilon) = q\) (empty string keeps the same state)
• Extended Transition Function (Recursive): \(\delta^*(q, y\sigma) = \delta(\delta^*(q, y), \sigma)\) (process string \(y\), then symbol \(\sigma\))
• String Acceptance: A string \(x \in \Sigma^*\) is accepted by \(M\) if \(\delta^*(q_0, x) \in F\)
• Language of an FSA: \(L(M) = \{x \in \Sigma^* \mid \delta^*(q_0, x) \in F\}\) (all strings accepted by \(M\))
• Incomplete Acceptance: For an incomplete FSA, \(x\) is accepted if all transitions \(q_k = \delta(q_{k-1}, c_k)\) are defined for each symbol in \(x\), and the final state is in \(F\)

---

4. Examples

4.1. Turnstile FSA with Formal Definition (Lab 3, Example 1)

Model a subway turnstile as an FSA. The turnstile has two states: Locked and Unlocked. Initially, it is Locked. The only way to make a transaction is to insert a Coin when Locked (transitions to Unlocked), then Push (transitions back to Locked). Pushing while Locked or inserting coins while Unlocked do nothing (remain in the same state). The accepting state is Locked (the proper state).

Click to see the solution

Step 1: Identify the components

Turnstile FSA

• States: Locked and Unlocked
• Alphabet: {Push, Coin}
• Initial state: Locked (the normal, secure state)
• Accepting state: Locked (transaction is complete)

Step 2: Define transitions

The transitions are:

• From Locked + Push → Locked (pushing while locked does nothing)
• From Locked + Coin → Unlocked (coin unlocks the gate)
• From Unlocked + Push → Locked (pushing passes through and relocks)
• From Unlocked + Coin → Unlocked (additional coins do nothing)

Step 3: Formal definition

\[M = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{\text{Locked}, \text{Unlocked}\}\)
• \(\Sigma = \{\text{Push}, \text{Coin}\}\)
• \(\delta\) is given by:

\(\delta\)	Push	Coin
Locked	Locked	Unlocked
Unlocked	Locked	Unlocked

• \(q_0 = \text{Locked}\)
• \(F = \{\text{Locked}\}\)

Step 4: Example strings

• \(\epsilon\) (empty string): Start at Locked (accepting) → ACCEPT
• “Push-Push”: Locked →Push→ Locked →Push→ Locked (accepting) → ACCEPT
• “Coin”: Locked →Coin→ Unlocked (not accepting) → REJECT
• “Push-Coin-Coin-Coin-Push”: Locked →Push→ Locked →Coin→ Unlocked →Coin→ Unlocked →Coin→ Unlocked →Push→ Locked (accepting) → ACCEPT

This FSA accepts exactly those sequences where every Coin is immediately followed (eventually) by a Push.

4.2. Simple Problem: What String Cannot Be Accepted? (Lab 3, Task 1)

Consider the FSA below. Which string cannot be accepted by this finite state automaton?

FSA Description:

• States: \(s_1\) (initial), \(s_2\), \(s_3\), \(s_4\) (accepting)
• Transitions:
  • \(s_1 \xrightarrow{a} s_2\)
  • \(s_2 \xrightarrow{a} s_2\) (loop)
  • \(s_2 \xrightarrow{b} s_1\)
  • \(s_2 \xrightarrow{c} s_4\)
  • \(s_4 \xrightarrow{d} s_3\)
  • \(s_3 \xrightarrow{a} s_1\)
  • \(s_3 \xrightarrow{b} s_4\)

Which of the following strings are rejected?

1. “ac”
2. “aaac”
3. “aaacda”
4. “aaacdb”

Click to see the solution

Key Concept: We trace through the FSA state by state. If at any point we encounter an undefined transition, the string is immediately rejected. If we reach the end and are not in an accepting state, the string is rejected.

FSA used to test which strings are accepted

Step 1: Analyze the FSA structure

The FSA has these transitions from each state:

• From \(s_1\): only ‘a’ is defined (goes to \(s_2\))
• From \(s_2\): ‘a’ (self-loop), ‘b’ (to \(s_1\)), ‘c’ (to \(s_4\))
• From \(s_3\): ‘a’ (to \(s_1\)), ‘b’ (to \(s_4\))
• From \(s_4\): only ‘d’ is defined (goes to \(s_3\))

Notice that no transition is defined from \(s_1\) for ‘b’, ‘c’, or ‘d’, and from \(s_4\) for ‘a’, ‘b’, or ‘c’.

Step 2: Test “ac”

• Start: \(s_1\)
• Read ‘a’: \(s_1 \xrightarrow{a} s_2\)
• Read ‘c’: \(s_2 \xrightarrow{c} s_4\)
• End state: \(s_4\) (accepting) → ACCEPT

Step 3: Test “aaac”

• Start: \(s_1\)
• Read ‘a’: \(s_1 \xrightarrow{a} s_2\)
• Read ‘a’: \(s_2 \xrightarrow{a} s_2\)
• Read ‘a’: \(s_2 \xrightarrow{a} s_2\)
• Read ‘c’: \(s_2 \xrightarrow{c} s_4\)
• End state: \(s_4\) (accepting) → ACCEPT

Step 4: Test “aaacda”

• Start: \(s_1\)
• Read ‘a’: \(s_1 \xrightarrow{a} s_2\)
• Read ‘a’: \(s_2 \xrightarrow{a} s_2\)
• Read ‘a’: \(s_2 \xrightarrow{a} s_2\)
• Read ‘c’: \(s_2 \xrightarrow{c} s_4\)
• Read ‘d’: \(s_4 \xrightarrow{d} s_3\)
• Read ‘a’: \(s_3 \xrightarrow{a} s_1\)
• End state: \(s_1\) (not accepting) → REJECT

Step 5: Test “aaacdb”

• Start: \(s_1\)
• Read ‘a’: \(s_1 \xrightarrow{a} s_2\)
• Read ‘a’: \(s_2 \xrightarrow{a} s_2\)
• Read ‘a’: \(s_2 \xrightarrow{a} s_2\)
• Read ‘c’: \(s_2 \xrightarrow{c} s_4\)
• Read ‘d’: \(s_4 \xrightarrow{d} s_3\)
• Read ‘b’: \(s_3 \xrightarrow{b} s_4\)
• End state: \(s_4\) (accepting) → ACCEPT

Answer: String (d) “aaacdb” can be tested, but based on the structure, strings that:

• Try to leave \(s_1\) with anything other than ‘a’
• Try to leave \(s_4\) with anything other than ‘d’
• End in a non-accepting state

The clearest rejection is (c) “aaacda” because it ends in \(s_1\), which is not accepting.

4.3. Binary Numbers Starting with 1 (Lab 3, Task 2)

Build a complete FSA that recognizes the language: \[L_1 = \{x \in \{0, 1\}^* \mid x \text{ starts with } 1\}\]

Examples: “1”, “10”, “11”, “100”, “101”, “110”, “111”, etc.

Click to see the solution

Key Concept: We need to recognize strings that begin with a 1. Once we read a 1 in the first position, we are in an accepting state. After that, any subsequent 0’s or 1’s keep us accepting.

Step 1: Design the states

• State \(q_0\) (initial): No symbols read yet. Not accepting.
• State \(q_1\): We have seen at least one 1, and we are ready to accept. Any continuation (0 or 1) keeps us accepting.
• State \(q_2\) (trap): We read a 0 first. No string starting with 0 is accepted. Stay here.

Step 2: Define transitions

From \(q_0\):

• Read 0 → go to \(q_2\) (starts with 0, reject)
• Read 1 → go to \(q_1\) (starts with 1, accept)

From \(q_1\):

• Read 0 → stay in \(q_1\) (still accepting)
• Read 1 → stay in \(q_1\) (still accepting)

From \(q_2\) (trap):

• Read 0 → stay in \(q_2\) (still rejecting)
• Read 1 → stay in \(q_2\) (still rejecting, because we started with 0)

Step 3: Formal FSA definition

\[M_1 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_0, q_1, q_2\}\)
• \(\Sigma = \{0, 1\}\)
• \(\delta\) is given by:

\(\delta\)	0	1
\(q_0\)	\(q_2\)	\(q_1\)
\(q_1\)	\(q_1\)	\(q_1\)
\(q_2\)	\(q_2\)	\(q_2\)

• \(q_0\) (initial)
• \(F = \{q_1\}\)

Step 4: Verify with examples

• “1”: \(q_0 \xrightarrow{1} q_1\) (accepting) → ACCEPT ✓
• “10”: \(q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_1\) (accepting) → ACCEPT ✓
• “0”: \(q_0 \xrightarrow{0} q_2\) (not accepting) → REJECT ✓
• “01”: \(q_0 \xrightarrow{0} q_2 \xrightarrow{1} q_2\) (not accepting) → REJECT ✓
• “101”: \(q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_1 \xrightarrow{1} q_1\) (accepting) → ACCEPT ✓

Complete FSA for binary strings starting with 1

This FSA is complete because every state has a transition for both 0 and 1.

4.4. Binary Numbers NOT Starting with 1 (Lab 3, Task 3)

Build a complete FSA that recognizes: \[L_2 = \{x \in \{0, 1\}^* \mid x \text{ does not begin with } 1\}\]

Examples: ““,”0”, “00”, “01”, “001”, “010”, etc.

Click to see the solution

Key Concept: This language includes the empty string (does not start with anything, so doesn’t start with 1) and all strings starting with 0. Once we see a 0 first, we accept, regardless of what follows.

Complete FSA for strings that do not start with 1

Step 1: Design the states

• State \(q_0\) (initial): No input yet. The empty string is accepted (it doesn’t start with 1).
• State \(q_1\): We have read a 0 first. Accept this and all continuations.
• State \(q_2\) (trap): We read a 1 first. Reject.

Step 2: Define transitions

From \(q_0\):

• Read 0 → go to \(q_1\) (starts with 0, accept)
• Read 1 → go to \(q_2\) (starts with 1, reject)

From \(q_1\):

• Read 0 → stay in \(q_1\)
• Read 1 → stay in \(q_1\)

From \(q_2\) (trap):

• Read 0 → stay in \(q_2\)
• Read 1 → stay in \(q_2\)

Step 3: Formal FSA definition

\[M_2 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_0, q_1, q_2\}\)
• \(\Sigma = \{0, 1\}\)
• \(\delta\) is given by:

\(\delta\)	0	1
\(q_0\)	\(q_1\)	\(q_2\)
\(q_1\)	\(q_1\)	\(q_1\)
\(q_2\)	\(q_2\)	\(q_2\)

• \(q_0\) (initial)
• \(F = \{q_0, q_1\}\) (both \(q_0\) and \(q_1\) are accepting)

Step 4: Verify with examples

• “” (empty): Start at \(q_0\) (accepting) → ACCEPT ✓
• “0”: \(q_0 \xrightarrow{0} q_1\) (accepting) → ACCEPT ✓
• “01”: \(q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_1\) (accepting) → ACCEPT ✓
• “1”: \(q_0 \xrightarrow{1} q_2\) (not accepting) → REJECT ✓
• “10”: \(q_0 \xrightarrow{1} q_2 \xrightarrow{0} q_2\) (not accepting) → REJECT ✓

4.5. Any 0 Followed by at Least One 1 (Lab 3, Task 4)

Build a complete FSA that recognizes: \[L_3 = \{x \in \{0, 1\}^* \mid \text{any } 0 \text{ in } x \text{ is followed by at least one } 1\}\]

Examples: “010111”, “1111”, “01110111011”

Valid strings have no 0 that is immediately followed by the end of the string or by another 0.

Click to see the solution

Key Concept: Every time we see a 0, the very next symbol must be a 1 (or the string must end with something else eventually). Actually, reading more carefully: “any 0 in \(x\) is followed by at least a 1” means if there is a 0, it must be followed by a 1. More strictly, we cannot have:

• 0 at the end of the string
• 00 (0 followed by 0)

Step 1: Design the states

• State \(q_0\) (initial): Just read a 1 or nothing. Ready to accept.
• State \(q_1\): Just read a 0. Must immediately see a 1 next.
• State \(q_2\) (trap): Either we saw a 0 followed by 0, or we’re at the end after a 0. Reject.

Step 2: Define transitions

From \(q_0\):

• Read 0 → go to \(q_1\) (we have a 0, need to see 1 next)
• Read 1 → stay in \(q_0\) (multiple 1’s are fine)

From \(q_1\):

• Read 0 → go to \(q_2\) (two consecutive 0’s, invalid)
• Read 1 → go to \(q_0\) (0 is properly followed by 1)

From \(q_2\) (trap):

• Read 0 → stay in \(q_2\)
• Read 1 → stay in \(q_2\)

Step 3: Formal FSA definition

\[M_3 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_0, q_1, q_2\}\)
• \(\Sigma = \{0, 1\}\)
• \(\delta\) is given by:

\(\delta\)	0	1
\(q_0\)	\(q_1\)	\(q_0\)
\(q_1\)	\(q_2\)	\(q_0\)
\(q_2\)	\(q_2\)	\(q_2\)

• \(q_0\) (initial)
• \(F = \{q_0\}\) (only \(q_0\) is accepting)

Step 4: Verify with examples

• “1111”: \(q_0 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{1} q_0\) (accepting) → ACCEPT ✓
• “010111”: \(q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{1} q_0\) (accepting) → ACCEPT ✓
• “01110111011”: \(q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_0\) (accepting) → ACCEPT ✓
• “10”: \(q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1\) (NOT accepting, because we end in \(q_1\)) → REJECT ✓
• “100”: \(q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2\) (not accepting) → REJECT ✓

Complete FSA where every 0 must be immediately followed by 1

4.6. Binary Strings Ending with 00 (Lab 3, Task 5)

Build a complete FSA that recognizes: \[L_4 = \{x \in \{0, 1\}^* \mid x \text{ ends with } 00\}\]

Examples: “00”, “100”, “1100”, “00100”

Click to see the solution

Key Concept: We need to track whether the last two symbols were both 0. We need states to remember: (1) no 0’s at the end, (2) one 0 at the end, (3) two 0’s at the end (accepting).

Complete FSA for binary strings ending with 00

Step 1: Design the states

• State \(q_0\) (initial): No 0’s at the end (just read a 1, or no input yet, or just started).
• State \(q_1\): Last symbol was 0, but the one before was not.
• State \(q_2\) (accepting): Last two symbols are 00.

Step 2: Define transitions

From \(q_0\):

• Read 0 → go to \(q_1\) (we have one 0 at the end)
• Read 1 → stay in \(q_0\) (no 0 at the end)

From \(q_1\):

• Read 0 → go to \(q_2\) (now two 0’s at the end)
• Read 1 → go to \(q_0\) (the 0 is no longer at the end)

From \(q_2\):

• Read 0 → stay in \(q_2\) (still two 0’s at the end: the previous 0 and the new 0)
• Read 1 → go to \(q_0\) (no 0’s at the end now)

Step 3: Formal FSA definition

\[M_4 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_0, q_1, q_2\}\)
• \(\Sigma = \{0, 1\}\)
• \(\delta\) is given by:

\(\delta\)	0	1
\(q_0\)	\(q_1\)	\(q_0\)
\(q_1\)	\(q_2\)	\(q_0\)
\(q_2\)	\(q_2\)	\(q_0\)

• \(q_0\) (initial)
• \(F = \{q_2\}\)

Step 4: Verify with examples

• “00”: \(q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2\) (accepting) → ACCEPT ✓
• “100”: \(q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2\) (accepting) → ACCEPT ✓
• “1100”: \(q_0 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2\) (accepting) → ACCEPT ✓
• “101”: \(q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_0\) (not accepting) → REJECT ✓

4.7. Binary Strings with Exactly 3 Zeros (Lab 3, Task 6)

Build a complete FSA that recognizes: \[L_5 = \{x \in \{0, 1\}^* \mid x \text{ contains exactly } 3 \text{ zeros}\}\]

Examples: “000”, “0001”, “1010100”, “11001001”

Click to see the solution

Key Concept: We need to count the number of 0’s. We create states corresponding to: 0 zeros seen, 1 zero seen, 2 zeros seen, 3 zeros seen, and more than 3 zeros (all rejected).

Complete FSA for binary strings containing exactly three 0s

Step 1: Design the states

• State \(q_0\) (initial): 0 zeros seen so far.
• State \(q_1\): 1 zero seen so far.
• State \(q_2\): 2 zeros seen so far.
• State \(q_3\) (accepting): Exactly 3 zeros seen so far.
• State \(q_4\) (trap): More than 3 zeros seen. Reject.

Step 2: Define transitions

From each state, reading a 1 keeps the count the same. Reading a 0 increments the count (moving to the next state) until we reach 4 zeros, at which point we go to the trap state.

From \(q_0\):

• Read 0 → go to \(q_1\)
• Read 1 → stay in \(q_0\)

From \(q_1\):

• Read 0 → go to \(q_2\)
• Read 1 → stay in \(q_1\)

From \(q_2\):

• Read 0 → go to \(q_3\)
• Read 1 → stay in \(q_2\)

From \(q_3\):

• Read 0 → go to \(q_4\) (too many zeros)
• Read 1 → stay in \(q_3\)

From \(q_4\) (trap):

• Read 0 → stay in \(q_4\)
• Read 1 → stay in \(q_4\)

Step 3: Formal FSA definition

\[M_5 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_0, q_1, q_2, q_3, q_4\}\)
• \(\Sigma = \{0, 1\}\)
• \(\delta\) is given by:

\(\delta\)	0	1
\(q_0\)	\(q_1\)	\(q_0\)
\(q_1\)	\(q_2\)	\(q_1\)
\(q_2\)	\(q_3\)	\(q_2\)
\(q_3\)	\(q_4\)	\(q_3\)
\(q_4\)	\(q_4\)	\(q_4\)

• \(q_0\) (initial)
• \(F = \{q_3\}\)

Step 4: Verify with examples

• “000”: \(q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_3\) (accepting) → ACCEPT ✓
• “0001”: \(q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{1} q_3\) (accepting) → ACCEPT ✓
• “1010100”: \(q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_4\) (not accepting) → REJECT ✓
• “11001001”: \(q_0 \xrightarrow{1} q_0 \xrightarrow{1} q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_4\) (not accepting) → REJECT ✓

4.8. Every a Followed by bb (Lab 3, Task 7)

Build a complete FSA that recognizes: \[L_6 = \{x \in \{a, b\}^* \mid \text{every } a \text{ in } x \text{ is followed immediately by } bb\}\]

Examples: ““,”b”, “bb”, “abbabb”, “bbbabbb”

Click to see the solution

Key Concept: Whenever we see an ‘a’, it must be immediately followed by ‘b’ and then another ‘b’. So the pattern “abb” must appear (no other ’a’s allowed unless they follow the same rule).

Step 1: Design the states

• State \(q_0\) (initial/accepting): We can accept here. No incomplete ‘abb’ pattern.
• State \(q_1\): We just read an ‘a’. Must see ‘b’ next.
• State \(q_2\): We just read ‘ab’. Must see ‘b’ next (to complete ‘abb’).
• State \(q_3\) (trap): Violation detected (e.g., ‘a’ not followed by ‘bb’, or other invalid pattern).

Step 2: Define transitions

From \(q_0\):

• Read ‘a’ → go to \(q_1\) (start the ‘abb’ pattern)
• Read ‘b’ → stay in \(q_0\) (isolated ’b’s are fine)

From \(q_1\):

• Read ‘a’ → go to \(q_3\) (two ’a’s in a row, violates the rule)
• Read ‘b’ → go to \(q_2\) (halfway through ‘abb’)

From \(q_2\):

• Read ‘a’ → go to \(q_3\) (after ‘ab’, we have ‘a’ instead of ‘b’, violation)
• Read ‘b’ → go to \(q_0\) (‘abb’ is complete, back to accepting)

From \(q_3\) (trap):

• Read ‘a’ → stay in \(q_3\)
• Read ‘b’ → stay in \(q_3\)

Step 3: Formal FSA definition

\[M_6 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_0, q_1, q_2, q_3\}\)
• \(\Sigma = \{a, b\}\)
• \(\delta\) is given by:

\(\delta\)	a	b
\(q_0\)	\(q_1\)	\(q_0\)
\(q_1\)	\(q_3\)	\(q_2\)
\(q_2\)	\(q_3\)	\(q_0\)
\(q_3\)	\(q_3\)	\(q_3\)

• \(q_0\) (initial)
• \(F = \{q_0\}\)

Step 4: Verify with examples

• ““: At \(q_0\) (accepting) → ACCEPT ✓
• “b”: \(q_0 \xrightarrow{b} q_0\) (accepting) → ACCEPT ✓
• “bb”: \(q_0 \xrightarrow{b} q_0 \xrightarrow{b} q_0\) (accepting) → ACCEPT ✓
• “abb”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{b} q_0\) (accepting) → ACCEPT ✓
• “abbabb”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{b} q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{b} q_0\) (accepting) → ACCEPT ✓
• “ab”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2\) (not accepting) → REJECT ✓
• “aba”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{a} q_3\) (not accepting) → REJECT ✓

4.9. Ends with b and No aa (Lab 3, Task 8)

Build a complete FSA that recognizes: \[L_7 = \{x \in \{a, b\}^* \mid x \text{ ends with } b \text{ and does not contain the substring } aa\}\]

Examples: “b”, “ab”, “bab”, “abb”, “abab”, “babab”

Non-examples: “a”, “aa”, “baa”, “aba” (ends with ‘a’), “aab” (contains “aa”)

Click to see the solution

Key Concept: We need to satisfy two conditions simultaneously: (1) no “aa” substring anywhere, and (2) end with ‘b’. We track: just saw ‘a’ or ‘b’, and keep rejecting if we ever see ‘aa’.

Step 1: Design the states

• State \(q_0\) (initial): Just saw ‘b’ or starting. Can accept if we’re done.
• State \(q_1\): Just saw an ‘a’ (and before that was ‘b’ or nothing, not ‘a’).
• State \(q_2\) (trap): Detected ‘aa’, or stuck in a state that cannot end correctly.

Note: Only \(q_0\) is accepting (we’re in the state where the last character was ‘b’).

Step 2: Define transitions

From \(q_0\):

• Read ‘a’ → go to \(q_1\) (we have an ‘a’, but so far no ‘aa’)
• Read ‘b’ → stay in \(q_0\) (still ending with ‘b’)

From \(q_1\):

• Read ‘a’ → go to \(q_2\) (now we have ‘aa’, violation)
• Read ‘b’ → go to \(q_0\) (now we’re ending with ‘b’, which is good)

From \(q_2\) (trap):

• Read ‘a’ → stay in \(q_2\)
• Read ‘b’ → stay in \(q_2\)

Step 3: Formal FSA definition

\[M_7 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_0, q_1, q_2\}\)
• \(\Sigma = \{a, b\}\)
• \(\delta\) is given by:

\(\delta\)	a	b
\(q_0\)	\(q_1\)	\(q_0\)
\(q_1\)	\(q_2\)	\(q_0\)
\(q_2\)	\(q_2\)	\(q_2\)

• \(q_0\) (initial)
• \(F = \{q_0\}\)

Step 4: Verify with examples

• “b”: \(q_0 \xrightarrow{b} q_0\) (accepting) → ACCEPT ✓
• “ab”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0\) (accepting) → ACCEPT ✓
• “bab”: \(q_0 \xrightarrow{b} q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0\) (accepting) → ACCEPT ✓
• “abb”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0 \xrightarrow{b} q_0\) (accepting) → ACCEPT ✓
• “a”: \(q_0 \xrightarrow{a} q_1\) (not accepting) → REJECT ✓
• “aa”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_2\) (not accepting) → REJECT ✓
• “aab”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_2 \xrightarrow{b} q_2\) (not accepting) → REJECT ✓
• “aba”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0 \xrightarrow{a} q_1\) (not accepting) → REJECT ✓

4.10. Contains Substring abbaab (Lab 3, Task 9)

Build a complete FSA that recognizes: \[L_8 = \{x \in \{a, b\}^* \mid x \text{ contains the substring } abbaab\}\]

Examples: “abbaab”, “aabbaab”, “abbaabc” (actually “abbaabb”), “ababbaab”

Click to see the solution

Key Concept: We need to recognize when the substring “abbaab” appears. We can use a state machine that tracks our progress toward completing “abbaab”. Once found, any subsequent symbols are fine.

Step 1: Design the states

• State \(q_0\) (initial): Haven’t started matching “abbaab” yet.
• State \(q_1\): Matched “a”.
• State \(q_2\): Matched “ab”.
• State \(q_3\): Matched “abb”.
• State \(q_4\): Matched “abba”.
• State \(q_5\): Matched “abbaa”.
• State \(q_6\) (accepting): Matched “abbaab”. Once here, any subsequent symbol keeps us here (accepting).

Step 2: Define transitions

The key is to follow the pattern. If we’re building “abbaab” and we read an unexpected character, we may need to backtrack to a suitable state.

From \(q_0\):

• Read ‘a’ → go to \(q_1\) (start matching)
• Read ‘b’ → stay in \(q_0\) (not the start of “abbaab”)

From \(q_1\):

• Read ‘a’ → stay in \(q_1\) (restart the match with ‘a’)
• Read ‘b’ → go to \(q_2\) (continue)

From \(q_2\):

• Read ‘a’ → go to \(q_1\) (reset: ‘a’ is the start of the pattern again)
• Read ‘b’ → go to \(q_3\) (continue)

From \(q_3\):

• Read ‘a’ → go to \(q_4\) (continue)
• Read ‘b’ → stay in \(q_3\) (back to just “abb”)

From \(q_4\):

• Read ‘a’ → go to \(q_5\) (continue)
• Read ‘b’ → go to \(q_0\) (no progress; ‘b’ doesn’t fit)

From \(q_5\):

• Read ‘a’ → stay in \(q_1\) (reset, ‘a’ is a potential start)
• Read ‘b’ → go to \(q_6\) (complete! “abbaab” found)

From \(q_6\) (accepting):

• Read ‘a’ → stay in \(q_6\) (already found the substring)
• Read ‘b’ → stay in \(q_6\) (already found the substring)

Step 3: Formal FSA definition

\[M_8 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_0, q_1, q_2, q_3, q_4, q_5, q_6\}\)
• \(\Sigma = \{a, b\}\)
• \(\delta\) is given by:

\(\delta\)	a	b
\(q_0\)	\(q_1\)	\(q_0\)
\(q_1\)	\(q_1\)	\(q_2\)
\(q_2\)	\(q_1\)	\(q_3\)
\(q_3\)	\(q_4\)	\(q_3\)
\(q_4\)	\(q_5\)	\(q_0\)
\(q_5\)	\(q_1\)	\(q_6\)
\(q_6\)	\(q_6\)	\(q_6\)

• \(q_0\) (initial)
• \(F = \{q_6\}\)

Step 4: Verify with examples

• “abbaab”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{b} q_3 \xrightarrow{a} q_4 \xrightarrow{a} q_5 \xrightarrow{b} q_6\) (accepting) → ACCEPT ✓
• “aabbaab”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{b} q_3 \xrightarrow{a} q_4 \xrightarrow{a} q_5 \xrightarrow{b} q_6\) (accepting) → ACCEPT ✓

4.11. Even Number of a’s and b’s (Lab 3, Task 10)

Build a complete FSA that recognizes: \[L_9 = \{x \in \{a, b\}^* \mid x \text{ has an even number of } a\text{'s and an even number of } b\text{'s}\}\]

Examples: ““,”aabb”, “abab”, “aabbab”, “baba” (2 a’s, 2 b’s, both even)

Click to see the solution

Key Concept: We need to track the parity (even/odd count) of both ‘a’ and ‘b’ separately. This requires 4 states:

• (even a’s, even b’s) — accepting
• (even a’s, odd b’s)
• (odd a’s, even b’s)
• (odd a’s, odd b’s)

Step 1: Design the states

• State \(q_{00}\) (initial/accepting): Even number of ’a’s, even number of ’b’s.
• State \(q_{01}\): Even number of ’a’s, odd number of ’b’s.
• State \(q_{10}\): Odd number of ’a’s, even number of ’b’s.
• State \(q_{11}\): Odd number of ’a’s, odd number of ’b’s.

Step 2: Define transitions

Each ‘a’ toggles the parity of ‘a’s (even ↔︎ odd). Each ’b’ toggles the parity of ’b’s.

From \(q_{00}\):

• Read ‘a’ → go to \(q_{10}\) (odd a’s now)
• Read ‘b’ → go to \(q_{01}\) (odd b’s now)

From \(q_{01}\):

• Read ‘a’ → go to \(q_{11}\) (now odd a’s and odd b’s)
• Read ‘b’ → go to \(q_{00}\) (b’s toggle back to even)

From \(q_{10}\):

• Read ‘a’ → go to \(q_{00}\) (a’s toggle back to even)
• Read ‘b’ → go to \(q_{11}\) (now odd a’s and odd b’s)

From \(q_{11}\):

• Read ‘a’ → go to \(q_{01}\) (a’s toggle back to even, b’s still odd)
• Read ‘b’ → go to \(q_{10}\) (b’s toggle back to even, a’s still odd)

Step 3: Formal FSA definition

\[M_9 = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_{00}, q_{01}, q_{10}, q_{11}\}\)
• \(\Sigma = \{a, b\}\)
• \(\delta\) is given by:

\(\delta\)	a	b
\(q_{00}\)	\(q_{10}\)	\(q_{01}\)
\(q_{01}\)	\(q_{11}\)	\(q_{00}\)
\(q_{10}\)	\(q_{00}\)	\(q_{11}\)
\(q_{11}\)	\(q_{01}\)	\(q_{10}\)

• \(q_{00}\) (initial)
• \(F = \{q_{00}\}\)

Step 4: Verify with examples

• ““: At \(q_{00}\) (accepting) → ACCEPT ✓
• “aabb”: \(q_{00} \xrightarrow{a} q_{10} \xrightarrow{a} q_{00} \xrightarrow{b} q_{01} \xrightarrow{b} q_{00}\) (accepting) → ACCEPT ✓
• “abab”: \(q_{00} \xrightarrow{a} q_{10} \xrightarrow{b} q_{11} \xrightarrow{a} q_{01} \xrightarrow{b} q_{00}\) (accepting) → ACCEPT ✓
• “a”: \(q_{00} \xrightarrow{a} q_{10}\) (not accepting) → REJECT ✓
• “aab”: \(q_{00} \xrightarrow{a} q_{10} \xrightarrow{a} q_{00} \xrightarrow{b} q_{01}\) (not accepting) → REJECT ✓

4.12. Binary Divisible by 5 Starting with 1 (Lab 3, Task 11)

Build a complete FSA that recognizes: \[L_{10} = \{x \in \{0, 1\}^* \mid x \text{ is a binary representation of an integer divisible by 5 and it begins with } 1\}\]

Examples: “101” (5 in binary), “1010” (10), “1111” (15), “11001” (25)

Click to see the solution

Key Concept: A number is divisible by 5 iff its remainder when divided by 5 is 0. We build states tracking the remainder modulo 5 as we read bits left to right. Each new bit doubles the previous value (or doubles and adds 1).

If the current remainder is \(r\), and we read bit \(b\):

• New remainder = \((2r + b) \mod 5\)

We need states for remainders 0, 1, 2, 3, 4. Only remainder 0 is accepting.

Step 1: Design the states

• State \(q_0\) (initial): Nothing read yet. Not accepting (we need at least “1”).
• State \(q_1\): Just read “1” (remainder 1 mod 5). Continue from here.
• State \(q_2\): Current remainder 2 mod 5.
• State \(q_3\): Current remainder 3 mod 5.
• State \(q_4\): Current remainder 4 mod 5.
• State \(q_5\) (accepting): Current remainder 0 mod 5.
• State \(q_6\) (trap): Started with 0 (doesn’t start with 1). Reject.

Step 2: Compute transitions

For each state \(q_i\) (representing remainder \(i\)) and bit \(b \in \{0, 1\}\): \[q_{(2i + b) \mod 5}\]

From \(q_0\) (initial, remainder undefined / 0):

• Read 0 → go to \(q_6\) (starts with 0, invalid)
• Read 1 → go to \(q_1\) (remainder 1)

From \(q_1\) (remainder 1):

• Read 0 → remainder = \((2 \cdot 1 + 0) \mod 5 = 2\) → go to \(q_2\)
• Read 1 → remainder = \((2 \cdot 1 + 1) \mod 5 = 3\) → go to \(q_3\)

From \(q_2\) (remainder 2):

• Read 0 → remainder = \((2 \cdot 2 + 0) \mod 5 = 4\) → go to \(q_4\)
• Read 1 → remainder = \((2 \cdot 2 + 1) \mod 5 = 0\) → go to \(q_5\)

From \(q_3\) (remainder 3):

• Read 0 → remainder = \((2 \cdot 3 + 0) \mod 5 = 6 \mod 5 = 1\) → go to \(q_1\)
• Read 1 → remainder = \((2 \cdot 3 + 1) \mod 5 = 7 \mod 5 = 2\) → go to \(q_2\)

From \(q_4\) (remainder 4):

• Read 0 → remainder = \((2 \cdot 4 + 0) \mod 5 = 8 \mod 5 = 3\) → go to \(q_3\)
• Read 1 → remainder = \((2 \cdot 4 + 1) \mod 5 = 9 \mod 5 = 4\) → go to \(q_4\)

From \(q_5\) (remainder 0, accepting):

• Read 0 → remainder = \((2 \cdot 0 + 0) \mod 5 = 0\) → stay in \(q_5\)
• Read 1 → remainder = \((2 \cdot 0 + 1) \mod 5 = 1\) → go to \(q_1\)

From \(q_6\) (trap):

• Read 0 → stay in \(q_6\)
• Read 1 → stay in \(q_6\)

Step 3: Formal FSA definition

\[M_{10} = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_0, q_1, q_2, q_3, q_4, q_5, q_6\}\)
• \(\Sigma = \{0, 1\}\)
• \(\delta\) is given by:

\(\delta\)	0	1
\(q_0\)	\(q_6\)	\(q_1\)
\(q_1\)	\(q_2\)	\(q_3\)
\(q_2\)	\(q_4\)	\(q_5\)
\(q_3\)	\(q_1\)	\(q_2\)
\(q_4\)	\(q_3\)	\(q_4\)
\(q_5\)	\(q_5\)	\(q_1\)
\(q_6\)	\(q_6\)	\(q_6\)

• \(q_0\) (initial)
• \(F = \{q_5\}\)

Step 4: Verify with examples

• “101” (5 in binary): \(q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_5\) (accepting) → ACCEPT ✓
• “1010” (10): \(q_0 \xrightarrow{1} q_1 \xrightarrow{0} q_2 \xrightarrow{1} q_5 \xrightarrow{0} q_5\) (accepting) → ACCEPT ✓
• “1111” (15): \(q_0 \xrightarrow{1} q_1 \xrightarrow{1} q_3 \xrightarrow{1} q_2 \xrightarrow{1} q_5\) (accepting) → ACCEPT ✓
• “1100” (12): \(q_0 \xrightarrow{1} q_1 \xrightarrow{1} q_3 \xrightarrow{0} q_1 \xrightarrow{0} q_2\) (not accepting) → REJECT ✓

4.13. Length ≥ 2 with Same Final Two Symbols (Lab 3, Task 12)

Build a complete FSA that recognizes: \[L_{11} = \{x \in \{0, 1\}^* \mid |x| \geq 2 \wedge \text{ final two symbols are the same}\}\]

Examples: “00”, “11”, “100”, “011”, “0100”

Click to see the solution

Key Concept: We need to track the last two symbols and ensure the string has at least 2 characters. States represent:

• Nothing read
• One symbol read
• Last two symbols are 00, 01, 10, or 11

Step 1: Design the states

• State \(q_0\) (initial): No symbols read.
• State \(q_1\): One symbol read (could be 0 or 1).
• State \(q_2\) (accepting): Last two are “00”.
• State \(q_3\): Last two are “01”.
• State \(q_4\): Last two are “10”.
• State \(q_5\) (accepting): Last two are “11”.

Step 2: Define transitions

From \(q_0\):

• Read 0 → go to \(q_1\) (we have read one 0)
• Read 1 → go to \(q_1\) (we have read one 1)

We need to track which symbol was read first. The refined states are:

• State \(q_{0}\) (initial): Nothing read.
• State \(q_{1a}\): One symbol “0” read.
• State \(q_{1b}\): One symbol “1” read.
• State \(q_{2}\) (accepting): Last two are “00”.
• State \(q_{3}\): Last two are “01”.
• State \(q_{4}\): Last two are “10”.
• State \(q_{5}\) (accepting): Last two are “11”.

From \(q_0\):

• Read 0 → go to \(q_{1a}\)
• Read 1 → go to \(q_{1b}\)

From \(q_{1a}\) (first symbol was 0):

• Read 0 → go to \(q_2\) (00)
• Read 1 → go to \(q_3\) (01)

From \(q_{1b}\) (first symbol was 1):

• Read 0 → go to \(q_4\) (10)
• Read 1 → go to \(q_5\) (11)

From \(q_2\) (ending with 00):

• Read 0 → stay in \(q_2\) (still 00)
• Read 1 → go to \(q_3\) (now 01)

From \(q_3\) (ending with 01):

• Read 0 → go to \(q_4\) (now 10)
• Read 1 → go to \(q_5\) (now 11)

From \(q_4\) (ending with 10):

• Read 0 → go to \(q_2\) (now 00)
• Read 1 → go to \(q_3\) (now 01)

From \(q_5\) (ending with 11):

• Read 0 → go to \(q_4\) (now 10)
• Read 1 → stay in \(q_5\) (still 11)

Step 3: Formal FSA definition

\[M_{11} = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{q_0, q_{1a}, q_{1b}, q_2, q_3, q_4, q_5\}\)
• \(\Sigma = \{0, 1\}\)
• \(\delta\) is given by:

\(\delta\)	0	1
\(q_0\)	\(q_{1a}\)	\(q_{1b}\)
\(q_{1a}\)	\(q_2\)	\(q_3\)
\(q_{1b}\)	\(q_4\)	\(q_5\)
\(q_2\)	\(q_2\)	\(q_3\)
\(q_3\)	\(q_4\)	\(q_5\)
\(q_4\)	\(q_2\)	\(q_3\)
\(q_5\)	\(q_4\)	\(q_5\)

• \(q_0\) (initial)
• \(F = \{q_2, q_5\}\)

Step 4: Verify with examples

• “00”: \(q_0 \xrightarrow{0} q_{1a} \xrightarrow{0} q_2\) (accepting) → ACCEPT ✓
• “01”: \(q_0 \xrightarrow{0} q_{1a} \xrightarrow{1} q_3\) (not accepting) → REJECT ✓
• “11”: \(q_0 \xrightarrow{1} q_{1b} \xrightarrow{1} q_5\) (accepting) → ACCEPT ✓
• “100”: \(q_0 \xrightarrow{1} q_{1b} \xrightarrow{0} q_4 \xrightarrow{0} q_2\) (accepting) → ACCEPT ✓
• “0100”: \(q_0 \xrightarrow{0} q_{1a} \xrightarrow{1} q_3 \xrightarrow{0} q_4 \xrightarrow{0} q_2\) (accepting) → ACCEPT ✓
• “0”: \(q_0 \xrightarrow{0} q_{1a}\) (not accepting) → REJECT ✓

4.14. Substring abc Appears Odd Number of Times (Lab 3, Task 13)

Build a complete FSA that recognizes: \[L_{12} = \{x \in \{a, b, c\}^* \mid \text{the substring } abc \text{ in } x \text{ occurs an odd number of times}\}\]

Click to see the solution

Key Concept: Track parity of “abc” occurrences modulo 2, plus KMP-style progress toward the next “abc”. Completing “abc” flips parity and resets progress to 0.

Step 1: Design the states

States \((s, p)\) where \(s \in \{E, O\}\) (even/odd count) and \(p \in \{0, 1, 2\}\) (chars matched so far). Notation: \(E0, E1, E2, O0, O1, O2\).

Step 2: Formal FSA definition

\[M_{12} = (\{E0, E1, E2, O0, O1, O2\},\ \{a, b, c\},\ \delta,\ E0,\ \{O0\})\]

\(\delta\)	a	b	c
\(E0\)	\(E1\)	\(E0\)	\(E0\)
\(E1\)	\(E1\)	\(E2\)	\(E0\)
\(E2\)	\(E1\)	\(E0\)	\(O0\)
\(O0\)	\(O1\)	\(O0\)	\(O0\)
\(O1\)	\(O1\)	\(O2\)	\(O0\)
\(O2\)	\(O1\)	\(O0\)	\(E0\)

Step 3: Verify with examples

• “abc”: \(E0 \xrightarrow{a} E1 \xrightarrow{b} E2 \xrightarrow{c} O0\) (accepting) → ACCEPT ✓
• “abcabc”: \(\ldots \xrightarrow{c} O0 \xrightarrow{a} O1 \xrightarrow{b} O2 \xrightarrow{c} E0\) (not accepting) → REJECT ✓
• “abcabcabc”: \(E0 \xrightarrow{abc} O0 \xrightarrow{abc} E0 \xrightarrow{abc} O0\) (accepting) → ACCEPT ✓
• ““: at \(E0\) (not accepting) → REJECT ✓

4.15. Marble Toy FSA (Lab 3, Homework 1)

Model a marble toy as a complete FSA. The toy has two input points (A and B) and two output points (C and D). Three levers (X1, X2, X3) control the path:

• A marble enters at A or B
• X1 is below A, X3 is below B, X2 is in the center
• Each lever, when hit, reverses its state for the next marble
• We want to model acceptance as the marble exiting at D (rejection is exiting at C)

Click to see the solution

Key Concept: Each lever has two states: it can redirect a marble left or right, and it flips after each marble passes. The state of the toy is the combination of the three lever states.

Step 1: Understand the marble flow

• From A: marble hits X1. If X1 is “left”, goes to C. If X1 is “right”, goes to X2.
• From B: marble hits X3. If X3 is “left”, goes to X2. If X3 is “right”, goes to D.
• From X2: If X2 is “left”, goes to C. If X2 is “right”, goes to D.

Each lever flips after a marble passes through it.

Step 2: Design the states

The state of the system is \((s_1, s_2, s_3)\) where each \(s_i \in \{L, R\}\) (Left or Right) is the current position of lever \(i\).

Initial state: Let’s say all levers are in the Left position initially: \((L, L, L)\).

We have \(2^3 = 8\) possible states:

• \((L, L, L)\) (initial)
• \((L, L, R)\)
• \((L, R, L)\)
• \((L, R, R)\)
• \((R, L, L)\)
• \((R, L, R)\)
• \((R, R, L)\)
• \((R, R, R)\)

Step 3: Define transitions

For input “A” (marble enters at A):

• Hits X1. After passing, X1 flips.
  • If X1 was L → goes to C, X1 becomes R
  • If X1 was R → goes to X2, which flips, and X2’s position determines if we go to C or D, then X2 becomes opposite
    • If X2 was L → goes to C, X2 becomes R
    • If X2 was R → goes to D, X2 becomes L

For input “A”: 1. Marble enters at A and immediately encounters X1. 2. Depending on X1’s state, the marble goes left (to C) or right (to X2). 3. If it goes to X2, it encounters X2, which redirects it to C or D based on X2’s state. 4. Levers flip after the marble passes through them: X1 always flips. X2 flips only if the marble reaches it.

Step 4: Compute transitions for input “A”

For each state \((s_1, s_2, s_3)\) and input “A”:

• If \(s_1 = L\): Marble goes left (to C) immediately. X1 flips to R. New state: \((R, s_2, s_3)\). Output: Reject (C).
• If \(s_1 = R\): Marble goes right to X2. X1 flips to L.
  • If \(s_2 = L\): At X2, marble goes left (to C). X2 flips to R. New state: \((L, R, s_3)\). Output: Reject (C).
  • If \(s_2 = R\): At X2, marble goes right (to D). X2 flips to L. New state: \((L, L, s_3)\). Output: Accept (D).

Step 5: Compute transitions for input “B”

For input “B”, the marble enters at B and hits X3.

• If \(s_3 = L\): Marble goes left (to X2). X3 flips to R.
  • If \(s_2 = L\): At X2, marble goes left (to C). X2 flips to R. New state: \((s_1, R, R)\). Output: Reject.
  • If \(s_2 = R\): At X2, marble goes right (to D). X2 flips to L. New state: \((s_1, L, R)\). Output: Accept.
• If \(s_3 = R\): Marble goes right (to D) immediately. X3 flips to L. New state: \((s_1, s_2, L)\). Output: Accept (D).

Step 6: Model definition

We define accepting states as those that are reached after processing an input where the marble exits at D. By computing all state transitions based on the lever mechanics:

Step 7: Formal FSA Definition

\[M_{\text{marble}} = (Q, \Sigma, \delta, q_0, F)\]

where:

• \(Q = \{(L,L,L), (R,L,L), (L,R,L), (R,R,L), (L,L,R), (R,L,R), (L,R,R), (R,R,R)\}\)
• \(\Sigma = \{A, B\}\)
• \(\delta\) is given by:

\(\delta\)	A	B
\((L,L,L)\)	\((R,L,L)\)	\((L,R,R)\)
\((R,L,L)\)	\((L,R,L)\)	\((R,R,R)\)
\((L,R,L)\)	\((R,R,L)\)	\((L,L,R)\)
\((R,R,L)\)	\((L,L,L)\)	\((R,L,R)\)
\((L,L,R)\)	\((R,L,R)\)	\((L,L,L)\)
\((R,L,R)\)	\((L,R,R)\)	\((R,L,L)\)
\((L,R,R)\)	\((R,R,R)\)	\((L,R,L)\)
\((R,R,R)\)	\((L,R,R)\)	\((R,R,L)\)

• \(q_0 = (L,L,L)\) (initial, but non-accepting initially)
• \(F = \{(L,L,L), (L,L,R), (R,L,R), (L,R,R), (R,R,R)\}\)

Step 8: Verification with Examples

• “A”: \((L,L,L) \xrightarrow{A} (R,L,L)\) (non-accepting) → REJECT ✓
• “AB”: \((L,L,L) \xrightarrow{A} (R,L,L) \xrightarrow{B} (R,R,R)\) (accepting) → ACCEPT ✓
• “BA”: \((L,L,L) \xrightarrow{B} (L,R,R) \xrightarrow{A} (R,R,R)\) (accepting) → ACCEPT ✓

4.16. Light Switch FSA (Lecture 3, Example 1)

Model a light switch as an FSA where toggling the switch alternates between On and Off states.

Click to see the solution

Key Concept: Two states alternating based on input, modeling a toggle mechanism.

1. Define components:
   • States: \(Q = \{\text{On}, \text{Off}\}\)
   • Alphabet: \(\Sigma = \{\text{T}\}\) (toggle)
   • Initial state: \(q_0 = \text{Off}\) (light starts off)
   • Accepting state: \(F = \{\text{On}\}\) (light is on)
2. Define transitions (\(\delta\)):
   • On + T → Off (toggle from on to off)
   • Off + T → On (toggle from off to on)
3. Formal definition: \[M = (\{\text{On}, \text{Off}\}, \{\text{T}\}, \delta, \text{Off}, \{\text{On}\})\]

Verification:

• “T”: Off \(\xrightarrow{T}\) On → ACCEPT (1 toggle, light on) ✓
• “TT”: Off \(\xrightarrow{T}\) On \(\xrightarrow{T}\) Off → REJECT (2 toggles, light off) ✓
• “TTT”: Off \(\xrightarrow{T}\) On \(\xrightarrow{T}\) Off \(\xrightarrow{T}\) On → ACCEPT (3 toggles, light on) ✓

Answer: The FSA accepts strings with an odd number of toggles (when the light ends in the On state).

4.17. Video Game AI: Pac-Man Ghost Behavior (Lecture 3, Example 2)

Model the behavior of a ghost in Pac-Man as an FSA with four behavioral states.

Click to see the solution

Key Concept: FSAs can model complex game AI behavior by representing different behavioral modes as states.

1. Define states (behaviors):
   • Wander: Ghost patrols the maze
   • Chase: Ghost actively pursues Pac-Man
   • Flee: Ghost runs away (after power pellet)
   • Return to Base: Ghost returns to respawn point
2. Define transitions (events):
   • Wander → Chase: Event: “Spot Pac-Man”
   • Chase → Flee: Event: “Pac-Man Eats Power Pellet”
   • Flee → Wander: Event: “Power Pellet Expires”
   • Chase → Return to Base: Event: “Eaten by Pac-Man”
   • Return to Base → Wander: Event: “Reach Central Base”
3. Initial state: Wander (default behavior)
4. Accepting states: Depends on game design (possibly any state is valid)

Key Point: This demonstrates that FSAs can model complex behavior using states and condition-based transitions. Real video game AIs use more sophisticated systems, but the principles are rooted in finite state machines.

Answer: 4-state FSA modeling different ghost behaviors with event-driven transitions.

4.18. Compiler Application: Pascal Identifier Recognition (Lecture 3, Example 3)

Design an FSA to recognize valid Pascal identifiers. A valid identifier starts with a letter and is followed by zero or more letters or digits.

Click to see the solution

Key Concept: Use states to track whether we’ve seen a valid start (letter) and accept continued letters/digits.

Language Specification:

• Must start with a letter
• Followed by zero or more letters or digits
• Examples: “x”, “count”, “var123”, “i”
• Non-examples: “123count” (starts with digit), “?” (invalid character)

1. Design states:
   • \(q_0\) (initial): Haven’t seen anything yet
   • \(q_1\) (accepting): Seen valid identifier (starts with letter)
   • \(q_E\) (trap/error): Invalid input
2. Define transitions:
   • From \(q_0\):
     • <letter> → \(q_1\) (valid start)
     • <digit> → \(q_E\) (invalid, must start with letter)
     • <other> → \(q_E\) (invalid character)
   • From \(q_1\) (accepting):
     • <letter> → \(q_1\) (continue accepting)
     • <digit> → \(q_1\) (continue accepting)
     • <other> → \(q_E\) (invalid)
   • From \(q_E\) (trap):
     • <any> → \(q_E\) (stay trapped)
3. Formal definition: \[M_{\text{Pascal ID}} = (\{q_0, q_1, q_E\}, \Sigma, \delta, q_0, \{q_1\})\] where \(\Sigma = \{\text{letters}, \text{digits}, \text{other}\}\)

Verification:

• “count”: \(q_0 \xrightarrow{c} q_1 \xrightarrow{o} q_1 \xrightarrow{u} q_1 \xrightarrow{n} q_1 \xrightarrow{t} q_1\) → ACCEPT ✓
• “var123”: \(q_0 \xrightarrow{v} q_1 \xrightarrow{a} q_1 \xrightarrow{r} q_1 \xrightarrow{1} q_1 \xrightarrow{2} q_1 \xrightarrow{3} q_1\) → ACCEPT ✓
• “123var”: \(q_0 \xrightarrow{1} q_E\) → REJECT ✓

Answer: 3-state FSA with \(q_1\) accepting after seeing a letter, then accepting letters/digits indefinitely. This is how lexers in compilers recognize identifiers.

4.19. Simple FSA: Recognizing “ba” (Tutorial 3, Example 1)

Design an FSA that accepts only the string “ba”.

Click to see the solution

Key Concept: Build a sequential path through states, one state for each position in the target string.

1. Design the states:
   • \(q_0\) (initial): No input yet
   • \(q_1\): After reading ‘b’
   • \(q_2\) (accepting): After reading ‘ba’
2. Define transitions:
   • \(q_0 \xrightarrow{b} q_1\)
   • \(q_1 \xrightarrow{a} q_2\)
   • All other transitions undefined (incomplete FSA)
3. Verification:
   • “ba”: \(q_0 \xrightarrow{b} q_1 \xrightarrow{a} q_2\) (accepting) → ACCEPT ✓
   • “ab”: \(q_0 \xrightarrow{a}\) undefined → REJECT ✓

Answer: The FSA has three states with a linear path from \(q_0\) to \(q_2\) spelling out “ba”.

4.20. Simple FSA: Recognizing “aba” (Tutorial 3, Example 2)

Design an FSA that accepts only the string “aba”.

Click to see the solution

Key Concept: Similar to the previous example, create a path matching each symbol.

1. Design the states:
   • \(q_0\) (initial): No input yet
   • \(q_1\): After reading ‘a’
   • \(q_2\): After reading ‘ab’
   • \(q_3\) (accepting): After reading ‘aba’
2. Define transitions:
   • \(q_0 \xrightarrow{a} q_1\)
   • \(q_1 \xrightarrow{b} q_2\)
   • \(q_2 \xrightarrow{a} q_3\)
3. Verification:
   • “aba”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{a} q_3\) (accepting) → ACCEPT ✓

Answer: The FSA has four states forming a linear path spelling “aba”.

4.21. Complete FSA for “ba” with Trap State (Tutorial 3, Example 3)

Convert the FSA recognizing “ba” to a complete FSA by adding a trap state.

Click to see the solution

Key Concept: A complete FSA has all transitions defined. Add a trap state for any undefined transitions.

1. Start with the incomplete FSA:
   • States: \(q_0\) (initial), \(q_1\), \(q_2\) (accepting)
   • Defined transitions: \(q_0 \xrightarrow{b} q_1\), \(q_1 \xrightarrow{a} q_2\)
2. Add trap state \(q_3\):
   • All undefined transitions lead to \(q_3\)
   • From \(q_0\): ‘b’ → \(q_1\), ‘a’ → \(q_3\) (trap)
   • From \(q_1\): ‘a’ → \(q_2\), ‘b’ → \(q_3\) (trap)
   • From \(q_2\): ‘a’ → \(q_3\), ‘b’ → \(q_3\) (both lead to trap)
   • From \(q_3\): ‘a’ → \(q_3\), ‘b’ → \(q_3\) (self-loops)
3. Verify completeness: Every state has transitions for both ‘a’ and ‘b’

Answer: The complete FSA has 4 states with \(q_3\) as a trap state that handles all invalid inputs.

4.22. Complete FSA for “aba” with Trap State (Tutorial 3, Example 4)

Convert the FSA recognizing “aba” to a complete FSA.

Click to see the solution

Key Concept: Same process as before—add a trap state for all undefined transitions.

1. Add trap state \(q_4\):
   • From \(q_0\): ‘a’ → \(q_1\), ‘b’ → \(q_4\)
   • From \(q_1\): ‘b’ → \(q_2\), ‘a’ → \(q_4\)
   • From \(q_2\): ‘a’ → \(q_3\), ‘b’ → \(q_4\)
   • From \(q_3\): ‘a’ → \(q_4\), ‘b’ → \(q_4\) (accepting state, any input goes to trap)
   • From \(q_4\): ‘a’ → \(q_4\), ‘b’ → \(q_4\) (trap loops)
2. Result: Complete FSA with 5 states

Answer: States \(q_0, q_1, q_2, q_3\) (accepting), \(q_4\) (trap), with all transitions defined.

4.23. FSA for Language with Multiple Accepting States (Tutorial 3, Example 5)

Design an FSA that accepts exactly the strings “a” and “aba”: \(L = \{a, aba\}\).

Click to see the solution

Key Concept: Use multiple accepting states—one for each string we want to accept.

1. Design states:
   • \(q_0\) (initial): No input
   • \(q_1\) (accepting): Read “a”
   • \(q_2\): Read “ab”
   • \(q_3\) (accepting): Read “aba”
2. Define transitions:
   • From \(q_0\): ‘a’ → \(q_1\)
   • From \(q_1\): ‘b’ → \(q_2\)
   • From \(q_2\): ‘a’ → \(q_3\)
   • Other transitions go to trap state (if we want complete FSA)
3. Accepting states: \(F = \{q_1, q_3\}\) (two accepting states)

Verification:

• “a”: \(q_0 \xrightarrow{a} q_1\) (accepting) → ACCEPT ✓
• “aba”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2 \xrightarrow{a} q_3\) (accepting) → ACCEPT ✓
• “ab”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_2\) (not accepting) → REJECT ✓

Answer: The FSA has multiple accepting states \(\{q_1, q_3\}\) to recognize multiple distinct strings.

4.24. FSA for Language Including Empty String (Tutorial 3, Example 6)

Design an FSA that accepts \(L = \{\epsilon, ba\}\) (the empty string and “ba”).

Click to see the solution

Key Concept: Make the initial state accepting to include \(\epsilon\) in the language.

1. Design states:
   • \(q_0\) (initial, accepting): Accepts \(\epsilon\)
   • \(q_1\): Read ‘b’
   • \(q_2\) (accepting): Read “ba”
2. Define transitions:
   • From \(q_0\): ‘b’ → \(q_1\)
   • From \(q_1\): ‘a’ → \(q_2\)
3. Accepting states: \(F = \{q_0, q_2\}\)

Verification:

• \(\epsilon\): Stay in \(q_0\) (accepting) → ACCEPT ✓
• “ba”: \(q_0 \xrightarrow{b} q_1 \xrightarrow{a} q_2\) (accepting) → ACCEPT ✓
• “b”: \(q_0 \xrightarrow{b} q_1\) (not accepting) → REJECT ✓

Answer: Initial state \(q_0\) is accepting, allowing \(\epsilon\) to be accepted.

4.25. FSA Accepting All Strings (Tutorial 3, Example 7)

Design an FSA that accepts every possible string over \(\Sigma = \{0, 1\}\): \(L = \Sigma^*\).

Click to see the solution

Key Concept: Use a single accepting state that loops on all symbols.

1. Design states: Just one state \(q_0\) (initial and accepting)
2. Define transitions:
   • From \(q_0\): ‘0’ → \(q_0\) (self-loop)
   • From \(q_0\): ‘1’ → \(q_0\) (self-loop)
3. Accepting states: \(F = \{q_0\}\)

Why it works: Since \(q_0\) is both initial and accepting, we accept before reading anything (\(\epsilon\)), and all transitions loop back to \(q_0\), so we remain accepting after reading any string.

Answer: Single-state FSA where the state is both initial and accepting, with self-loops for all symbols.

4.26. FSA Accepting Empty Language (Tutorial 3, Example 8)

Design an FSA that accepts no strings at all: \(L = \emptyset\).

Click to see the solution

Key Concept: Have no reachable accepting states.

1. Design states:
   • \(q_0\) (initial, non-accepting)
   • Optionally \(q_1\) (accepting, but unreachable)
2. Define transitions:
   • From \(q_0\): ‘0’ → \(q_0\), ‘1’ → \(q_0\) (loops)
   • State \(q_1\) is unreachable
3. Accepting states: \(F = \{q_1\}\) or \(F = \emptyset\)

Why it works: The initial state is not accepting, and there’s no way to transition to an accepting state. Therefore, no string is ever accepted.

Answer: FSA with non-accepting initial state and no reachable accepting states.

4.27. Infinite Regular Language: Strings Starting with 0 (Tutorial 3, Example 9)

Design an FSA to recognize \(L = \{w \in \{0, 1\}^* : w \text{ starts with } 0\}\).

Click to see the solution

Key Concept: Once we verify the first symbol is 0, accept all subsequent strings. This shows FSAs can recognize infinite languages.

1. Design states:
   • \(q_0\) (initial): Haven’t seen anything yet
   • \(q_1\) (accepting): Seen ‘0’ at the beginning
   • \(q_2\) (rejecting): Seen ‘1’ first (wrong start)
2. Define transitions:
   • From \(q_0\):
     • Read ‘0’ → go to \(q_1\) (good start)
     • Read ‘1’ → go to \(q_2\) (bad start)
   • From \(q_1\) (accepting):
     • Read ‘0’ → stay in \(q_1\) (still accepting)
     • Read ‘1’ → stay in \(q_1\) (still accepting)
   • From \(q_2\) (rejecting):
     • Read ‘0’ → stay in \(q_2\) (still rejecting)
     • Read ‘1’ → stay in \(q_2\) (still rejecting)

Verification:

• “0”: \(q_0 \xrightarrow{0} q_1\) → ACCEPT ✓
• “01101”: \(q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_1 \xrightarrow{1} q_1 \xrightarrow{0} q_1 \xrightarrow{1} q_1\) → ACCEPT ✓
• “1000”: \(q_0 \xrightarrow{1} q_2\) (stays in \(q_2\)) → REJECT ✓

Key Insight: Once we see the initial 0, we stay in an accepting state forever. This allows the FSA to accept infinitely many strings.

Answer: 3-state FSA accepting all strings starting with ‘0’.

4.28. Infinite Regular Language: Repetitions of “ab” (Tutorial 3, Example 10)

Design an FSA to recognize \(L = \{(ab)^k : k \in \mathbb{N}\} = \{\epsilon, ab, abab, ababab, ...\}\).

Click to see the solution

Key Concept: Use states to track progress through the pattern “ab”, returning to the accepting state after each complete repetition.

1. Design states:
   • \(q_0\) (initial and accepting): Completed 0 or more full “ab” patterns
   • \(q_1\): Seen ‘a’, need ‘b’ to complete pattern
   • \(q_2\) (trap): Invalid pattern detected
2. Define transitions:
   • From \(q_0\):
     • Read ‘a’ → go to \(q_1\) (start of “ab”)
     • Read ‘b’ → go to \(q_2\) (invalid, ‘b’ without ‘a’ first)
   • From \(q_1\):
     • Read ‘b’ → go to \(q_0\) (completed “ab”, return to accepting)
     • Read ‘a’ → go to \(q_2\) (invalid, two ’a’s in a row)
   • From \(q_2\) (trap):
     • Read ‘a’ or ‘b’ → stay in \(q_2\)

Verification:

• \(\epsilon\): Stay in \(q_0\) (accepting) → ACCEPT ✓
• “ab”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0\) (accepting) → ACCEPT ✓
• “abab”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0\) → ACCEPT ✓
• “aba”: \(q_0 \xrightarrow{a} q_1 \xrightarrow{b} q_0 \xrightarrow{a} q_1\) (not accepting) → REJECT ✓

Answer: 3-state FSA with \(q_0\) accepting, cycling through states for each “ab” pattern.

4.29. Understanding Non-Regular Languages (Tutorial 3, Example 11)

Important Concept: Not all infinite languages are regular. Consider \(L = \{a^k b^k : k \in \mathbb{N}\}\).

Click to see the solution

Key Concept: This language requires counting, which FSAs cannot do with finite memory.

The Language: \[L = \{a^k b^k : k \in \mathbb{N}\} = \{\epsilon, ab, aabb, aaabbb, aaaabbbb, ...\}\]

This language consists of strings with equal numbers of ’a’s followed by equal numbers of ’b’s.

Why FSAs Cannot Recognize This:

1. Finite states mean finite memory: An FSA with \(n\) states can only “remember” \(n\) different configurations
2. Counting requires unbounded memory: To verify \(a^k b^k\), we must count how many ’a’s we saw, which could be arbitrarily large
3. Pigeonhole principle: After seeing \(n+1\) ’a’s, by the pigeonhole principle, the FSA must be in the same state as after seeing some smaller number of ’a’s. It cannot distinguish between different counts.

Answer: This language is not regular. FSAs have insufficient memory to count arbitrarily. We need more powerful models like Pushdown Automata (with a stack) or Turing Machines (with a tape) to recognize such languages.